// LUOGU_RID: 111078019
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
ll x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=2e5+5;
int n,a[maxn];
struct node{
int l,r;
node* ch[2];
int mn,cnt,fs,add=0;
void pushup(){
mn=min(ch[0]->mn,ch[1]->mn);
cnt=0;
if(mn==ch[1]->mn){
cnt+=ch[1]->cnt;
fs=ch[1]->fs;
}
if(mn==ch[0]->mn){
cnt+=ch[0]->cnt;
fs=ch[0]->fs;
}
}
node(int l,int r):l(l),r(r),mn(l-1),cnt(1),fs(l){
if(l==r) return;
int mid=l+(r-l)/2;
ch[0]=new node(l,mid);
ch[1]=new node(mid+1,r);
}
void pushtag(int k){
mn+=k;
add+=k;
}
void pushdown(){
ch[0]->pushtag(add);
ch[1]->pushtag(add);
add=0;
}
void modify(int ql,int qr,int k){
if(ql>r||qr<l) return;
if(ql<=l&&qr>=r){
pushtag(k);
return;
}
pushdown();
ch[0]->modify(ql,qr,k);
ch[1]->modify(ql,qr,k);
pushup();
}
~node(){
if(l==r) return;
delete ch[0];
delete ch[1];
}
}*rt;
set<int> st;
int s[maxn],tp,mn[maxn],mx[maxn],p1[maxn],p2[maxn];
bool t1[maxn],t2[maxn];
ll calc1(int x){
return 1ll*p1[x]*(mn[x]-*--st.lower_bound(mn[x])-1);
}
ll calc2(int x){
return 1ll*p2[x]*(*st.upper_bound(mx[x])-mx[x]-1);
}
int s1[maxn],tp1,s2[maxn],tp2;
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
st={0,a[1],n+1};
s[tp=1]=s1[tp1=1]=s2[tp2=1]=1;
rt=new node(1,n);
mn[1]=mx[1]=a[1];
p1[1]=p2[1]=t1[1]=t2[1]=1;
auto C2=[](int x){
return 1ll*x*(x+1)/2;
};
ll ans=C2(a[1]-1)+C2(n-a[1])+n;
printf("%lld %lld",C2(n),ans);
for(int i=2;i<=n;i++){
int l=*--st.lower_bound(a[i]),r=*st.upper_bound(a[i]);
while(mn[s[tp]]>r||mx[s[tp]]<l){
ans--;
if(t1[s[tp]]) ans-=calc1(s[tp]);
if(t2[s[tp]]) ans-=calc2(s[tp]);
mn[s[tp-1]]=min(mn[s[tp-1]],mn[s[tp]]);
mx[s[tp-1]]=max(mx[s[tp-1]],mx[s[tp]]);
tp--;
}
mn[i]=mx[i]=a[i];
int x=lower_bound(s+1,s+tp+1,rt->fs)-s;
if(mn[s[tp]]>a[i]){
p1[i]=max(p1[s[tp]],tp-x+2);
t1[s[tp]]=0;
ans-=calc1(s[tp]);
}
else{
p1[i]=1;
if(!t1[s[tp]]){
t1[s[tp]]=1;
ans+=calc1(s[tp]);
}
}
if(mx[s[tp]]<a[i]){
p2[i]=max(p2[s[tp]],tp-x+2);
t2[s[tp]]=0;
ans-=calc2(s[tp]);
}
else{
p2[i]=1;
if(!t2[s[tp]]){
t2[s[tp]]=1;
ans+=calc2(s[tp]);
}
}
st.insert(a[i]);
t1[i]=t2[i]=1;
ans+=calc1(i)+calc2(i)+1;
s[++tp]=i;
ans+=rt->cnt+C2(r-a[i]-1)+C2(a[i]-l-1)-C2(r-l-1);
printf(" %lld",ans);
rt->pushtag(-1);
while(tp1&&a[i]<a[s1[tp1]]){
rt->modify(s1[tp1-1]+1,s1[tp1],a[s1[tp1]]);
tp1--;
}
rt->modify(s1[tp1]+1,i,-a[i]);
s1[++tp1]=i;
while(tp2&&a[i]>a[s2[tp2]]){
rt->modify(s2[tp2-1]+1,s2[tp2],-a[s2[tp2]]);
tp2--;
}
rt->modify(s2[tp2]+1,i,a[i]);
s2[++tp2]=i;
}
printf("\n");
delete rt;
}
#ifdef LOCAL
fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
1506D - Epic Transformation | 1354G - Find a Gift |
1426F - Number of Subsequences | 1146B - Hate "A" |
1718C - Tonya and Burenka-179 | 834A - The Useless Toy |
1407D - Discrete Centrifugal Jumps | 1095B - Array Stabilization |
291B - Command Line Arguments | 1174B - Ehab Is an Odd Person |
624B - Making a String | 1064C - Oh Those Palindromes |
1471A - Strange Partition | 1746A - Maxmina |
1746B - Rebellion | 66C - Petya and File System |
1746C - Permutation Operations | 1199B - Water Lily |
570B - Simple Game | 599C - Day at the Beach |
862A - Mahmoud and Ehab and the MEX | 1525A - Potion-making |
1744D - Divisibility by 2n | 1744A - Number Replacement |
1744C - Traffic Light | 1744B - Even-Odd Increments |
637B - Chat Order | 546C - Soldier and Cards |
18D - Seller Bob | 842B - Gleb And Pizza |